ارائه کلاسی GNN نیمسال جاری

مقدمه شبکه‌های عصبی گرافی

مقدمه و تعاریف پایه

در چشم‌انداز نوین یادگیری ماشین، گراف‌ها ابزاری بی‌رقیب برای مدل‌سازی روابط پیچیده بین موجودیت‌ها هستند. در حالی که در مدل‌های سنتی، داده‌ها معمولاً به‌صورت سطرهای مستقل یک جدول در نظر گرفته می‌شوند، دنیای واقعی سرشار از وابستگی و ارتباط است.

در داده‌های گرافی، «ساختار ارتباطات» (Structure) به اندازهٔ «ویژگی‌های گره‌ها» (Features) حاوی اطلاعات حیاتی است؛ نادیده گرفتن یال‌ها یعنی حذف بخش بزرگی از ماهیت مسئله، و دقیقاً همین‌جاست که شبکه‌های عصبی گرافی (GNN) وارد میدان می‌شوند.

ساختار ریاضی

یک گراف \(G\) را معمولاً به‌صورت \(G = (V, E)\) تعریف می‌کنند که در آن:

  • \(V\): مجموعه‌ی گره‌ها (Nodes) یا رأس‌ها؛ هر گره می‌تواند نشانگر یک فرد، شیء، مولکول یا سند باشد.
  • \(E\): مجموعه‌ی یال‌ها (Edges) که بیانگر رابطه یا تعامل بین دو گره است.

ورودی استاندارد یک GNN شامل دو مؤلفه کلیدی است:

  1. ماتریس ویژگی‌ها \(X\): اگر گراف \(N\) گره و هر گره \(D\) ویژگی داشته باشد، ماتریسی با ابعاد \(N \times D\) است که هر سطر آن بردار ویژگی یک گره را نشان می‌دهد.
  2. ماتریس مجاورت \(A\): ماتریسی که ساختار اتصالات را کدگذاری می‌کند؛ وجود یال بین گره \(i\) و \(j\) معمولاً با ۱ و نبود آن با صفر در درایه \(A_{ij}\) نشان داده می‌شود.

انتقال پیام (Message Passing)

قلب تپندهٔ محاسبات در GNNها، مکانیزم «ارسال پیام» است. در هر لایه، هر گره پیام‌هایی از همسایگان خود دریافت می‌کند، آن‌ها را تجمیع کرده و با وضعیت فعلی خودش ترکیب می‌کند تا به یک نمایش (Embedding) جدید و غنی‌تر برسد.

این فرایند سبب می‌شود که پس از چند لایه، هر گره نه‌تنها اطلاعات خودش، بلکه دانش ساختاری همسایگان نزدیک و دورتر را نیز در بردار ویژگی‌اش حمل کند.

فرمول به‌روزرسانی (Update Rule)

در قالب ریاضی، به‌روزرسانی وضعیت گره \(v\) در لایهٔ \(k\)-ام را می‌توان به‌شکل کلی زیر نوشت:

\[h_v^{(k)} = \sigma \left( W^{(k)} \cdot \text{AGGREGATE}\left( \{\, h_u^{(k-1)} : u \in \mathcal{N}(v) \,\} \right) \right)\]

  • \(h_v^{(k)}\): بردار تعبیه (Embedding) گره \(v\) در لایهٔ \(k\).
  • \(\mathcal{N}(v)\): مجموعهٔ همسایگان گره \(v\). نکته: در GNNها معمولاً خود گره \(v\) نیز به این مجموعه اضافه می‌شود (Self-loop) تا اطلاعات خودش حفظ شود.
  • \(h_u^{(k-1)}\): پیام‌های دریافتی از گره‌های همسایه در لایهٔ قبل.
  • \(\text{AGGREGATE}\): تابعی مستقل از ترتیب (مانند جمع، میانگین یا Max) که پیام‌ها را فشرده می‌کند.
  • \(W^{(k)}\): ماتریس وزن‌های قابل یادگیری شبکه.
  • \(\sigma\): تابع فعال‌ساز غیرخطی (مانند ReLU).

هدف نهایی این است که با تکرار این چرخه، برداری بسازیم که هم «محتوای گره» و هم «موقعیت آن در شبکه» را توصیف کند.


باشگاه کاراته زاخاری (Zachary’s Karate Club)

داستان داده‌ها

دیتاست Zachary’s Karate Club شبکهٔ اجتماعی ۳۴ عضو یک باشگاه کاراته دانشگاهی را روایت می‌کند. پس از یک اختلاف شدید بین مربی (Mr. Hi) و مدیر باشگاه (Officer)، این گروه عملاً دوشقه شد.

در این گراف، هر گره یک دانشجو و هر یال نشان‌دهنده تعاملات اجتماعی خارج از کلاس است. چالش کلاسیک یادگیری ماشین در اینجا این است: آیا می‌توانیم فقط با نگاه کردن به الگوی دوستی‌ها (ساختار گراف)، پیش‌بینی کنیم هر عضو به کدام جناح (مربی یا مدیر) پیوسته است؟

این سناریو به عنوان «Hello World» تحلیل شبکه شناخته می‌شود و بنچمارکی عالی برای تست الگوریتم‌های GNN است.


کتابخانه‌های تحلیل گراف در R

ابزارهای تحلیل

برای پیاده‌سازی و تصویرسازی این شبکه در زبان R، از مثلث قدرتمند igraph، tidygraph و ggraph استفاده می‌کنیم. این ابزارها زنجیرهٔ کامل «مدل‌سازی»، «دست‌کاری داده به روش Tidy» و «تصویرسازی لایه‌محور» را فراهم می‌کنند.

بارگذاری کتابخانه‌ها

کد زیر این بسته‌ها را فراخوانی می‌کند:

library(igraph)
library(tidygraph)
library(ggraph)
  • igraph: موتور محاسباتی گراف و الگوریتم‌های پایه.
  • tidygraph: رابطی که گراف را شبیه به جداول دیتابیس (Tibble) مدیریت می‌کند.
  • ggraph: افزونه‌ای بر ggplot2 برای رسم گراف‌های زیبا و گویا.

۱. آماده‌سازی داده‌ها و برچسب‌گذاری

هدف: ایجاد “Ground Truth”

در مسائل واقعی GNN، ما معمولاً برچسب‌ها را داریم و مدل را آموزش می‌دهیم. اما در این تحلیل اکتشافی، ما از یک الگوریتم خوشه‌بندی کلاسیک به نام Louvain استفاده می‌کنیم تا ببینیم گروه‌های طبیعی شبکه کجا هستند.

خروجی این مرحله، گرافی است که در آن برای هر گره، یک شماره گروه (Community) تعیین شده است. این شماره می‌تواند به عنوان برچسب (Label) برای آموزش یا تست یک GNN فرضی در نظر گرفته شود.

کد ساخت و پردازش

در قطعه کد زیر، گراف استاندارد زاخاری را می‌سازیم، آن را به فرمت Tidy تبدیل کرده و بلافاصله الگوریتم تشخیص اجتماع را روی آن اجرا می‌کنیم:

graph_data <- as_tbl_graph(make_graph("Zachary")) %>%
  mutate(community = factor(group_louvain()))

تابع group_louvain() با بهینه‌سازی معیار Modularity، گره‌هایی که اتصالات متراکم‌تری با هم دارند را در یک گروه قرار می‌دهد. این دقیقاً همان ساختاری است که GNNها نیز تلاش می‌کنند آن را یاد بگیرند.

الگوریتم Louvain چیست؟

الگوریتم Louvain یک روش غیر-عصبی (Non-neural) و حریصانه برای کشف جوامع در شبکه است. در گراف زاخاری، این الگوریتم معمولاً موفق می‌شود دو یا چند دستهٔ اصلی را جدا کند که انطباق بسیار بالایی با واقعیت تاریخی (جناح مربی و جناح مدیر) دارد. بنابراین، نتیجهٔ این الگوریتم تأیید می‌کند که ساختار گراف حاوی اطلاعات کافی برای جداسازی کلاس‌ها هست.


۲. تصویرسازی شبکه (Visualization)

تحلیل بصری

حال که گروه‌ها توسط الگوریتم مشخص شدند، شبکه را رسم می‌کنیم. هدف این است که ببینیم آیا گره‌های هم‌رنگ (هم‌گروه) در کنار هم قرار می‌گیرند یا خیر. در GNNها، فرض اصلی (Homophily) این است که گره‌های متصل به هم، ویژگی‌ها یا برچسب‌های مشابهی دارند.

رسم گراف با ggraph

از الگوریتم چیدمان Fruchterman-Reingold (fr) استفاده می‌کنیم که گره‌های متصل را فیزیکی به هم نزدیک‌تر می‌کند:

ggraph(graph_data, layout = 'fr') +
  geom_edge_link(color = "#94a3b8", alpha = 0.6, show.legend = FALSE) +
  geom_node_point(aes(color = community), size = 6) +
  scale_color_brewer(palette = "Set1") +
  theme_graph() +
  labs(title = "تحلیل ساختاری: خوشه‌های باشگاه کاراته",
       subtitle = "رنگ‌ها نشان‌دهنده جوامع کشف‌شده توسط الگوریتم Louvain هستند")

  • geom_edge_link: رسم یال‌ها (کمرنگ برای تمرکز بر گره‌ها).
  • geom_node_point: رسم گره‌ها با رنگ‌بندی بر اساس ستون community.

۳. جمع‌بندی نهایی

نتیجه‌گیری مشاهدات

تصویر خروجی به وضوح نشان می‌دهد که شبکه به چند قطب اصلی تقسیم شده است. الگوریتم Louvain صرفاً با تکیه بر یال‌ها توانست اعضا را دسته‌بندی کند. این همان کاری است که یک GNN به روشی پیچیده‌تر و با قابلیت تعمیم‌پیذیری بالاتر انجام می‌دهد: یادگیری بردار‌هایی که گره‌های متصل را در فضای برداری به هم نزدیک می‌کند تا دسته‌بندی آن‌ها ساده شود.

تحلیل ساختاری

گره‌های مرکزی (هاب‌ها) در وسط خوشه‌ها قرار دارند و اعضای مرزی نقش پل ارتباطی را بازی می‌کنند. این مثال ثابت می‌کند که در داده‌های شبکه‌ای، “به من بگو دوستانت کیستند تا بگویم کیستی” یک اصل علمی معتبر است. GNNها دقیقاً همین اصل را با مکانیزم “Message Passing” مدل‌سازی ریاضی می‌کنند.